package algorithm.leetcode.I201to400;

/**
 * 想象成由前缀聚合在一起的多叉树(类似英文词典)
 */

public class Q208 {

    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("app");
        trie.insert("apple");
        trie.insert("beer");
        trie.insert("add");
        trie.insert("jam");
        trie.insert("rental");

        System.out.println(trie.search("apps"));
        System.out.println(trie.search("app"));
    }
}



class Trie {
    Trie[] children;
    boolean isEnd;

    /** Initialize your data structure here. */
    public Trie() {
        children = new Trie[26];
        isEnd = false;
    }

    /** Inserts a word into the trie. */
    public void insert(String word) {
        Trie temp = this;  // 指向树的当前层
        for (int i = 0; i < word.length(); i++) {
            int index = word.charAt(i)-'a';
            // 如果这个单词从某个位置开始在前缀树中未出现过,那么新建
            if (temp.children[index] == null) temp.children[index] = new Trie();
            temp = temp.children[index];  // 指向当前层
        }
        temp.isEnd = true;  // 单词末尾的这一层用end标识单词已结束
    }

    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        Trie trie = searchPrefix(word);
        return trie != null && trie.isEnd;
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        return searchPrefix(prefix) != null;
    }

    private Trie searchPrefix(String word) {
        Trie temp = this;  // 指向树的当前层
        for (int i = 0; i < word.length(); i++) {
            int index = word.charAt(i)-'a';
            if (temp.children[index] == null) return null;
            temp = temp.children[index]; // 指向当前层
        }
        return temp;
    }

}